#include <iostream>
#include <queue>
#include <vector>

using std::cin;
using std::cout;
using std::queue;
using std::vector;
#define lld long long

void sol() {
  int V, E;
  cin >> V >> E;

  vector<vector<int>> G(V);
  vector<int> indegree(V, 0);
  for (int i = 0; i < E; ++i) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    // u 比 v better
    // v -> u
    G[v].emplace_back(u);
    indegree[u]++;
  }
  queue<int> q;
  vector<int> level(V, 0);
  vector<int> tp;
  int curr_level = 0;
  int vis_cnt = 0;
  auto topo = [&]() {
    for (int i = 0; i < V; ++i) {
      if (indegree[i] == 0) {
        q.push(i);
      }
    }
    while (!q.empty()) {
      int size = q.size();
      for (int j = 0; j < size; ++j) {
        int u = q.front();
        q.pop();
        level[u] = curr_level;
        vis_cnt++;
        for (auto v : G[u]) {
          indegree[v]--;
          if (indegree[v] == 0) {
            q.push(v);
          }
        }
      }
      curr_level++;
    }
  };

  topo();

  vector<int> bonus(V);
  if (vis_cnt != V) {
    for (int i = 0; i < V; ++i)
      bonus[i] = 888;
  } else {
    for (int i = 0; i < V; ++i)
      bonus[i] = 888 + level[i] * 1000;
  }

  lld sum = 0;
  for (auto x : bonus)
    sum += x;
  cout << sum << std::endl;

  for (int i = 0; i < V; ++i) {
    cout << bonus[i] << " ";
  }
  cout << std::endl;
}
int main() {
  int K;
  cin >> K;

  while (K--) {
    sol();
  }
  return 0;
}